// https://leetcode.cn/problems/longest-valid-parentheses/
// 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

#include <string>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
	// 最长的括号数，虽然和本题意思不一致
    int longestValidParentheses(string s) {
		int len = s.size();
		int num = 0;
		int left = 0;
		int right = 0;
		for(int i = 0; i < len; i++){
			cout << "i:" << i << endl;
			if(s[i] == '('){
				if(s[i+1] != ')'){
					// cout << 123 << endl;
					continue;
				}else{
					left = i;
					right = i + 1;
					while(left >= 0 && right < len && s[left] == '(' && s[right] == ')'){
						left--;
						right++;
						num++;
						i++;
					}
				}
			}
		}
		return num * 2;
    }
	
	
	int longestValidParentheses1(string s) {
		int len = s.size();
		stack<int> nums;
		vector<int> res;
		for(int i = 0; i < len; i++){
			if(s[i] == '('){
				nums.push(i);
			}else{
				if(nums.empty()){
					continue;
				}else{
					int top = nums.top();
					res.push_back(top);
					res.push_back(i);
					nums.pop();
				}
			}
		}
		if(res.empty()){
			return 0;
		}
		
		int num = 1;
		int tmpNum = 1;
		sort(res.begin(), res.end());
		int rLen = res.size();
		for(int j = 0; j < rLen; j++){
			if(j < rLen - 1 && (res[j + 1] - res[j]) <= 1){
				tmpNum++;
			}else{
				if(tmpNum > num){
					num = tmpNum;
				}
				tmpNum = 1; // 注意这里必须要复位
			}
		}

		if(tmpNum > num){
			num = tmpNum;
		}
		
		return num;
    }
};

int main(){
	Solution so;
	// string s= ")) ()(()) ) ()((()))() ) (((()("; 0 1 2 4
	// string s= "))()(()) )()((()))())(((()(";
	string s= ")(()(()(((())(((((()()))((((()()(()()())())())()))()()()())(())()()(((()))))()((()))(((())()((()()())((())))(())))())((()())()()((()((())))))((()(((((()((()))(()()(())))((()))()))())"; // 0 3
	int a = so.longestValidParentheses1(s);
	cout << a << endl;
	return 0;
}